package leetcode;

/**
 * leetcode 42.接雨水
 */
public class Leetcode42 {

    //DP
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length + 1];
        int[] maxRight = new int[height.length + 1];
        maxLeft[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            maxLeft[i] = Integer.max(maxLeft[i-1],height[i]);
        }
        maxRight[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0 ; i--) {
            maxRight[i] = Integer.max(maxRight[i+1],height[i]);
        }
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            sum += Integer.min(maxLeft[i],maxRight[i]) - height[i];
        }
        return sum;
    }

    public static void main(String[] args) {

    }
}
